Một bài toán tối ưu hóa lồi ở dạng chuẩn là nền tảng của lập trình toán học hiện đại. Nó được xác định bởi một hàm mục tiêu lồi $f_0$, các ràng buộc bất đẳng thức lồi $f_i$, và tuyến tính_affine ràng buộc đẳng thức. Bằng cách xác định bài toán trên giao của các miền này $\mathcal{D} = \bigcap_{i=0}^m \text{dom } f_i$, ta đảm bảo rằng mọi cực tiểu cục bộ đều là cực tiểu toàn cục.
1. Cấu trúc toán học của dạng chuẩn
Bài toán được nêu chính thức như sau:
Tập khả thi được định nghĩa là $\text{dom } F = \{x \in \text{dom } f_0 \mid f_i(x) \le 0, i = 1, \dots, m, h_i(x) = 0, i = 1, \dots, p \}$. Một yêu cầu quan trọng cho tính lồi là các ràng buộc đẳng thức phải tuyến tính_affine ($Ax = b$), vì các đẳng thức phi tuyến thường tạo ra các tập hợp không lồi.
2. Diễn giải hình học dạng epigraph
Dạng epigraph cho phép chúng ta diễn giải tối ưu hóa một cách hình học trong 'không gian đồ thị' $(x, t)$. Bằng cách giới thiệu biến dư $t$, ta tối thiểu hóa $t$ với điều kiện $(x, t) \in \text{epi } f_0$. Điều này chứng minh rằng tập khả thi, mọi tập con mức (sublevel set), và tập cực trị đều có bản chất lồi.
3. Sai lầm khi nhầm lẫn giữa ràng buộc ngầm và rõ ràng
Một hiểu lầm phổ biến là chuyển các ràng buộc vào hàm mục tiêu (làm chúng trở thành ngầm) sẽ đơn giản hóa bài toán. Tuy nhiên, việc làm cho các ràng buộc trở nên ngầm không hề làm cho bài toán dễ phân tích hay giải hơn, dù bài toán kết quả về mặt danh nghĩa là không có ràng buộc. Điều này đặc biệt đúng trong mô hình Oracle (hộp đen), nơi chúng ta đánh giá $f(x)$ và đạo hàm của nó với chi phí mà không biết cấu trúc rõ ràng.
4. Ứng dụng thực tế
- Lý thuyết danh mục đầu tư: Tối thiểu hóa rủi ro $\text{var}(c^T x) = x^T \Sigma x$ cho 4 tài sản (ví dụ: Tài sản 1 với lợi suất 12%/độ lệch chuẩn 20%).
- Kỹ thuật: Các ràng buộc cấu trúc như $y_i = 6(i - 1/3) \frac{F}{E w_i h_i^3} + v_{i+1} + y_{i+1}$.
- Xác suất: Các ràng buộc rủi ro tổn thất $\Phi^{-1}(\beta) \leq 0$.